GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Selectionsort</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Selectionsort</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Selectionsort (<a href="Englische_Sprache" title="Englische Sprache">englisch</a> selection ‚Auswahl‘ und <a href="Englische_Sprache" title="Englische Sprache">englisch</a> sort ‚sortieren‘) ist ein einfacher („naiver“) <a href="Sortierverfahren" title="Sortierverfahren">Sortieralgorithmus</a>, der <a href="In-place" class="mw-redirect" title="In-place">in-place</a> arbeitet und in seiner Grundform <a href="Stabilit%C3%A4t_(Sortierverfahren)" title="Stabilität (Sortierverfahren)">instabil</a> ist, wobei er sich auch <a href="Stabilit%C3%A4t_(Sortierverfahren)" title="Stabilität (Sortierverfahren)">stabil</a> implementieren lässt. Die <a href="Komplexit%C3%A4t_(Informatik)" title="Komplexität (Informatik)">Komplexität</a> von Selectionsort ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy"> (<a href="Landau-Notation" class="mw-redirect" title="Landau-Notation">Landau-Notation</a>). Alternative Bezeichnungen des Algorithmus sind MinSort (von Minimum) bzw. MaxSort (von Maximum), Selectsort oder ExchangeSort (AustauschSort).

<div class="mw-heading mw-heading2"><h2 id="Prinzip">Prinzip</h2></div>

Sei S der sortierte Teil des <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Arrays</a> (vorne im Array) und U der unsortierte Teil (dahinter). Am Anfang ist S noch leer, U entspricht dem ganzen (restlichen) Array. Das Sortieren durch Auswählen läuft nun folgendermaßen ab:

Suche das kleinste Element in U und vertausche es mit dem ersten Element von U (= das erste Element nach S).

Danach ist das Array bis zu dieser Position sortiert. Das kleinste Element wird in S verschoben (indem S einfach als ein Element länger betrachtet wird, und U nun ein Element später beginnt). S ist um ein Element gewachsen, U um ein Element kürzer geworden. Anschließend wird das Verfahren so lange wiederholt, bis das gesamte Array abgearbeitet worden ist; S umfasst am Ende das gesamte Array, aufsteigend sortiert, U ist leer.

<div class="mw-heading mw-heading3"><h3 id="Alternativen">Alternativen</h3></div>

Analog kann statt des kleinsten Elements das größte in U gesucht werden, was zu einer absteigenden Sortierreihenfolge führt. Auch kann U nach vorne und S nach hinten gelegt werden, was ebenfalls die Sortierreihenfolge umkehrt.

Zudem existieren auch Ansätze, in denen beide Varianten (MinSort und MaxSort) gemeinsam arbeiten; es gibt einen S-Bereich vorne und einen S-Bereich hinten, U liegt dazwischen. Während eines Durchlaufes werden das größte und das kleinste Element in U gesucht und dieses dann jeweils an den Anfang bzw. an das Ende von U gesetzt. Dadurch erreicht man in der Regel eine Beschleunigung, die jedoch meist nicht den Faktor 2 erreicht. Diese Variante wird gelegentlich „Optimized Selection Sort Algorithm“ (OSSA) genannt.

<div class="mw-heading mw-heading2"><h2 id="Formaler_Algorithmus">Formaler Algorithmus</h2></div>

Der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> sieht im <a href="Pseudocode" title="Pseudocode">Pseudocode</a> so aus:

<pre>prozedur SelectionSort( A : Liste sortierbarer Elemente )

hoechsterIndex = Elementanzahl( A ) - 1

einfuegeIndex = 0

wiederhole

minPosition = einfuegeIndex

für jeden idx von (einfuegeIndex + 1) bis hoechsterIndex wiederhole

falls A[ idx ] < A[ minPosition ] dann

minPosition = idx

ende falls

ende für

vertausche A[ minPosition ] und A[ einfuegeIndex ]

einfuegeIndex = einfuegeIndex + 1

solange einfuegeIndex < hoechsterIndex

prozedur ende

</pre>

Beispiel-Implementierung des <a href="Algorithmus" title="Algorithmus">Algorithmus</a> in <a href="BASIC" title="BASIC">BASIC</a>:

<div class="mw-highlight mw-highlight-lang-basic mw-content-ltr mw-highlight-lines" dir="ltr"><pre>Procedure SelectionSort ( Dim(1) A : Double )

Integer : Elemente, Ia, Small, Ib, MaxIndex

Double : TMP

Elemente = Count( A )

If Elemente < 2 Then Return

MaxIndex = Elemente - 1

For Ia = 0 To (MaxIndex - 1)

Small = Ia

For Ib = (Ia + 1) To MaxIndex

If A(Small) > A(Ib) Then Small = Ib

Next Ib

TMP = A(Ia)

A(Ia) = A(Small)

A(Small) = TMP

Next Ia

Return

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Beispiel">Beispiel</h2></div>

Es soll ein <a href="Feld_(Datentyp)" class="mw-redirect" title="Feld (Datentyp)">Array</a> mit dem Inhalt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [4|2|1|6|3|5]}">

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [4|2|1|6|3|5]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6c166d0fa664fb6f0e6493fa14680b39b4884d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.503ex; height:2.843ex;" alt="{\displaystyle [4|2|1|6|3|5]}" loading="lazy"> sortiert werden. Rot eingefärbte Felder deuten eine Tauschoperation an, blau eingefärbte Felder liegen im bereits sortierten Teil des Arrays.

<td>

<table>

<td>5

</td></tr></tbody></table>

</td>

<td>Das Minimum ist 1. Vertausche also das 1. und das 3. Element.

</td></tr>

<tr>

<td>

<table>

<td>5

</td></tr></tbody></table>

</td>

<td>Das Minimum des rechten Teilarrays ist 2. Da es bereits an 2. Position steht, wird es nicht getauscht.

</td></tr>

<tr>

<td>

<table>

<td>5

</td></tr></tbody></table>

</td>

<td>Wir haben jetzt bereits ein sortiertes Teilarray der Länge 2. Wir vertauschen nun 4 und das Minimum 3.

</td></tr>

<tr>

<td>

<table>

<td>5

</td></tr></tbody></table>

</td>

<td>Wir vertauschen 6 und 4.

</td></tr>

<tr>

<td>

<table>

<td class="hintergrundfarbe7">5

</td></tr></tbody></table>

</td>

<td>Wir vertauschen 6 und 5.

</td></tr>

<tr>

<td>

<table>

<td class="hintergrundfarbe6">6

</td></tr></tbody></table>

</td>

<td>Das Array ist jetzt fertig sortiert.

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Komplexität">Komplexität</h2></div>

Um ein Array mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> Einträgen mittels SelectionSort zu sortieren, muss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy">-mal das Minimum bestimmt und ebenso oft getauscht werden.

Bei der ersten Bestimmung des Minimums sind <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> Vergleiche notwendig, bei der zweiten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ff40d66ad535411eedb9c686a9008a5089c35ac0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-2}" loading="lazy"> Vergleiche usw.

Mit der <a href="Gau%C3%9Fsche_Summenformel" title="Gaußsche Summenformel">gaußschen Summenformel</a> erhält man die Anzahl der notwendigen Vergleiche:

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<msup>

</mrow>

</msup>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (n-1)+(n-2)+\dotsb +3+2+1={\frac {(n-1)\cdot n}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f1660b6d334435a53641778cfd55660399ba79dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:60.496ex; height:5.676ex;" alt="{\displaystyle (n-1)+(n-2)+\dotsb +3+2+1={\frac {(n-1)\cdot n}{2}}={\frac {n^{2}}{2}}-{\frac {n}{2}}}" loading="lazy"></dd></dl>

Da das erste Element <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fbd0b0f32b28f51962943ee9ede4fb34198a2521.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n-1}" loading="lazy"> ist, entspricht die exakte Schrittzahl nicht genau der Darstellung der Gaußformel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+(n-1)+\dotsb +2+1={\tfrac {n\cdot (n+1)}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+(n-1)+\dotsb +2+1={\tfrac {n\cdot (n+1)}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/871a5454a89403bd52c19b580af86432e2f3b691.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:34.756ex; height:4.176ex;" alt="{\displaystyle n+(n-1)+\dotsb +2+1={\tfrac {n\cdot (n+1)}{2}}}" loading="lazy">.

SelectionSort liegt somit in der Komplexitätsklasse <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n^{2})}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n^{2})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4441d9689c0e6b2c47994e2f587ac5378faeefba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.108ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}(n^{2})}" loading="lazy">.

Da zum Ermitteln des Minimums immer der komplette noch nicht sortierte Teil des Arrays durchlaufen werden muss, benötigt SelectionSort auch im „besten Fall“ <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tfrac {n\cdot (n-1)}{2}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\tfrac {n\cdot (n-1)}{2}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43b9872b53ac14f8e745ac6528840e20af56f41d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:6.646ex; height:4.176ex;" alt="{\displaystyle {\tfrac {n\cdot (n-1)}{2}}}" loading="lazy"> Vergleiche.

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a href="https://de.wikibooks.org/wiki/Algorithmensammlung:_Sortierverfahren:_Selectionsort" class="extiw external" title="b:Algorithmensammlung: Sortierverfahren: Selectionsort">Wikibooks: Selectionsort</a> – Implementierungen in der Algorithmensammlung</div>

<ul><li><a rel="nofollow" class="external free" href="https://www.sortieralgorithmen.de/selectsort/index.html">https://www.sortieralgorithmen.de/selectsort/index.html</a></li>

<li><a rel="nofollow" class="external text" href="http://www.danmor.ch/blog/?p=221">Erklärung und Code in C++</a></li>

<li><a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.654.4716&rep=rep1&type=pdf">OSSA – Vorstellung und Pseudocode</a> (PDF) <a rel="nofollow" class="external text" href="http://howtodevelop.eu/question/optimized-selection-sort-algorithm-ossa--how-to-fix-it,27307">OSSA bugfixed</a></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-08-11" href="https://de.wikipedia.org/wiki/?title=Selectionsort&oldid=247602918">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>